package sort;

/**
 * 块排
 * QuickSort
 */
public class QuickSort implements Sort{

    /**
     * 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
     *
     *   从数列中挑出一个元素，称为 “基准”（pivot）；
     *   重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
     *   递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
     */
	@Override
	public void sort(int[] array) {
        if(array.length < 2){
            return;
        }
        int first = 0;
        int last = array.length - 1;
        int pivotIndex=partition(array,first,last);  //定义pivotIndex中间位置。partition是检索这个方法
        quickSort(array,first,pivotIndex-1);              //排序左半边
        quickSort(array,pivotIndex+1,last);               //排序右半边

    }

    public  void quickSort(int[] a,int first,int last){
        if(first<last){                //至少两个位置
            int pivotIndex=partition(a,first,last);  //定义pivotIndex中间位置。partition是检索这个方法
            quickSort(a,first,pivotIndex-1);              //排序左半边
            quickSort(a,pivotIndex+1,last);               //排序右半边
        }
    }

	private int partition(int[] array, int left, int right) {

        int pivot=array[left];//先定义区间数组第一个元素为主元
        int i=left;   //定义最低的索引low是first+1。比主元大一位
        int j=right;     //定义最高的索引high是last
        while(i!=j){   //当low小于high的位置时，执行以下循环
        	while(array[j]>pivot && i<j){//当high的索引上的值比主元大时，且索引大于low时
                j--;                      //寻找比主元小的值的位置索引
            }
            while(array[i]<=pivot && i<j){//当low的索引上的值比主元小时，索引小于high时
                i++;                       //寻找比主元大的值的位置索引。
            }
            if(i<j){   //交换low和high的值
                int t=array[i];
                array[i]=array[j];
                array[j]=t;
            }
       }
        array[left]=array[j];
        array[j]=pivot;
        return j;
	}



}